from typing import List
from functools import cache
from math import inf
class Solution:
    def minCost(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3 :
            return max(nums)
        @cache 
        def dfs(i : int , pre : int) :
            if i >= n :
                return pre
            if i + 1 >= n :
                return max(pre , nums[i])
            p = [nums[i] , nums[i + 1] , pre]
            p.sort()
            # 要么选最小的两个，要么选最大的两个，否则没道理
            res = inf
            res = min(res , p[2] + dfs(i + 2 , p[0]))
            res = min(res , p[1] + dfs(i + 2 , p[2]))
            return res 
        ans = inf 
        q = [nums[0] , nums[1] , nums[2]]
        q.sort()
        ans = min(ans , dfs(3 , q[0]) + q[2])
        ans = min(ans , dfs(3 , q[2]) + q[1])
        return ans
    
    
min_cost = Solution().minCost

# 示例用法
nums1 = [6, 2, 8, 4]
print(min_cost(nums1))  # 输出应为 12

nums2 = [2, 1, 3, 3]
print(min_cost(nums2))  # 输出应为 5

nums3 =[10,8,10,10,9,7,6]
print(min_cost(nums3))